package practise.alogrithm.hundredInterviewQuestions.secondTime;

/**
 * Created by Richard on 7/27/2014.
 */
public class LongestPlindromicSubstring {
    public String length(String str){
        Boolean[][] matrix = new Boolean[str.length()][str.length()];// use a boolan is enough, we will compute the value from back
        Integer maxLength = -1, maxBegin=0;
        //single letter is a palindromic
        for(int index=0; index<str.length();index++){
            matrix[index][index]=true;
        }
        //the substring contain two letter
        for(int index=0; index<str.length()-1;index++){
            if(str.charAt(index+1)==str.charAt(index)){
                matrix[index][index+1]=true;
            }
        }

        for(int start=str.length()-3; start>=0;start--){
            for(int end=start+2;end<str.length()-1;end++){
                if(str.charAt(start)==str.charAt(end) && matrix[start+1][end-1]){
                    matrix[start][end]=true;
                    // the largest always in the end of the loop, keep updating
                    maxBegin = start;
                    maxLength=end-start+1;
                }
            }
        }
        return str.substring(maxBegin,maxBegin+maxLength);
    }

    public static void main(String[] args){
        System.out.print("result:"+ new LongestPlindromicSubstring().length("google"));
    }
}
